Search for: All records

Near-Optimal Bayesian Online Assortment of Reusable Resources Motivated by rental services in e-commerce, we consider revenue maximization in the online assortment of reusable resources for different types of arriving consumers. We design competitive online algorithms compared with the optimal online policy in the Bayesian setting, where consumer types are drawn independently from known heterogeneous distributions over time. In scenarios with large initial inventories, our main result is a near-optimal competitive algorithm for reusable resources. Our algorithm relies on an expected linear programming (LP) benchmark, solves this LP, and simulates the solution through independent randomized rounding. The main challenge is achieving inventory feasibility efficiently using these simulation-based algorithms. To address this, we design discarding policies for each resource, balancing inventory feasibility and revenue loss. Discarding a unit of a resource impacts future consumption of other resources, so we introduce postprocessing assortment procedures to design and analyze our discarding policies. Additionally, we present an improved competitive algorithm for nonreusable resources and evaluate our algorithms using numerical simulations on synthetic data. 

Two-Stage Matching and Pricing in Ride-Hailing Platforms Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem with or without pricing to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces, such as ride-hailing platforms. We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency and two-stage joint matching and pricing for maximizing market efficiency. Using various techniques, such as introducing convex programming–based matching and graph decompositions, submodular maximization, and factor-revealing linear programs, we obtain either optimal competitive or improved approximation algorithms compared with naïve solutions. We enrich our theoretical study by data-driven numerical simulations using DiDi’s ride-sharing data sets. 

In this paper we study the fundamental problems of maximizing a continuous nonmonotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first 1 2 -approximation algorithm for continuous submodular function maximization; this approximation factor of 1 2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular function is also coordinate-wise concave along all coordinates, we provide a different 1 2 -approximation algorithm that runs in quasi-linear time. Both these results improve upon prior work (Bian et al., 2017a,b; Soma and Yoshida, 2017). Our first algorithm uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zero-sum game for each coordinate, and incorporates the geometry of this zero-sum game to fix the value at this coordinate. Our second algorithm exploits coordinate-wise concavity to identify a monotone equilibrium condition sufficient for getting the required approximation guarantee, and hunts for the equilibrium point using binary search. We further run experiments to verify the performance of our proposed algorithms in related machine learning applications. 

This paper considers the problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. The main result is the first 1/2-approximation algorithm for continuous submodular function maximization; this approximation factor of 1/2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular functions are also coordinate-wise concave along all coordinates, we provide a different 1 2-approximation algorithm that runs in quasi-linear time.